#include <vector>
#include <iostream>
using namespace std;
// 堆是一个容器适配器
namespace zq
{
    // 如果我们要实现的小堆该怎么办呢
    // 可以使用仿函数或者lamda表达式
    template <class T>
    struct less
    { // 大堆
        bool operator()(const T &x1, const T &x2)
        {
            return x1 < x2;
        }
    };

    template <class T>
    struct greater
    { // 小堆
        bool operator()(const T &x1, const T &x2)
        {
            return x1 > x2;
        }
    };

    template <class T, class Container = vector<T>, class compare = less<T>>
    class Priority_queue
    {
    public:
        void AdjustUp(int child)
        {
            compare com;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (com(_con[parent], _con[child]))
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
        void push(const T &x)
        {
            _con.push_back(x); // 复用了容器的方法
            // 向上调整
            AdjustUp(_con.size() - 1);
        }

        // 堆的删除是删除堆顶的数据，也就是第一个位置的数据
        // 我们可以将堆顶的数据和最后一个位置的数据进行交换，然后再复用尾删的接口
        // 最后再继续维护堆的性质，也就是说将刚刚换到堆顶的数据进行一次向下调整算法
        void AdjustDown(int root)
        {
            compare com;
            int parent = root;
            int child = 2 * parent + 1;
            while (child < _con.size())
            {
                // 找出左右孩子中最大的那个
                if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
                {
                    child++;
                }
                if (com(_con[parent], _con[child]))
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }
        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();

            AdjustDown(0);
        }
        T &top()
        {
            return _con[0];
        }
        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }

    private:
        Container _con;
    };

} // namespace zq
